package com.dyz.leetcode._13_binaryTree;

public class _666_pathSum {
    /***
     对于一棵深度小于 5 的树，可以用一组三位十进制整数来表示。
     对于每个整数：
     百位上的数字表示这个节点的深度 D，1 <= D <= 4。
     十位上的数字表示这个节点在当前层所在的位置 P， 1 <= P <= 8。位置编号与一棵满二叉树的位置编号相同。
     个位上的数字表示这个节点的权值 V，0 <= V <= 9。

     样例 1:
     输入: [113, 215, 221]
     输出: 12
     解释:
     这棵树形状如下:
     3
     / \
     5   1
     路径和 = (3 + 5) + (3 + 1) = 12.


     样例 2:
     输入: [113, 221]
     输出: 4
     解释:
     这棵树形状如下:
     3
     \
     1
     路径和 = (3 + 1) = 4.

     */

    private int ans = 0;
    public int pathSum(int[] nums) {
        // 构建二叉树，使用数组存储
        Integer[] tree = new Integer[15];
        for (int num : nums) {
            int bai = num / 100;
            int shi = num % 100 / 10;
            int ge = num % 10;
            int index = ((1 << (bai - 1)) - 1) + shi - 1;
            tree[index] = ge;
        }

        // DFS 遍历树
        dfs(tree, 0, 0);
        return ans;
    }

    private void dfs(Integer[] tree, int i, int currPathSum) {
        if (tree[i] == null){ return;}

        currPathSum += tree[i];
        if (i >= 7 || (tree[2 * i + 1] == null && tree[2 * i + 2] == null)) {
            ans += currPathSum;
            return;
        }

        dfs(tree, 2 * i + 1, currPathSum);
        dfs(tree, 2 * i + 2, currPathSum);
    }
}
